package com.mzy.linear_struct;

import java.util.*;

/**
 * @Author: codermzy
 * @Date: 2024/04/17/15:59
 * @Description:
 */
public class Heap {

    private LinkedList<Integer> data = new LinkedList<>();
    private int length;


    public Heap() {
    }

    private void swap(int i, int j) {
        Integer temp = data.get(i);
        data.set(i, data.get(j));
        data.set(j, temp);
    }

    public void insert(Integer value) {
        /**
         * 1. 先将新元素67添加到数组尾部
         * 2. 检查是否符合最大堆特性
         * + 将新元素与父元素做比较（父元素=(index - 1)/2）、(子元素=)
         * + 如果父元素大于等于新元素，则直接 break
         * + 如果父元素小于新元素，交换父子元素，并且将索引修改为父元素的索引
         */
        // 先将新的元素添加到尾部
        data.add(value);
        length++;

        int index = length - 1;
        while (index > 0) {
            // 获取当前元素的父元素
            int parent = (index - 1) / 2;
            if (data.get(parent) >= data.get(index)) {
                break;
            }
            swap(parent, index);
            index = parent;

        }
    }

    public Integer extract() {
        // 1. 获取第一个元素(最大值)
        // 2. 将最后一个元素挪到第一个元素上，进行下滤操作
        // 3. 获取左子节点和右子节点
        //      左子节点：(2 * index + 1)
        //      右子节点：(2 * index + 2)

        Integer max = data.get(0);
        data.set(0, data.get(length - 1));
        data.removeLast();
        length--;
        int index = 0;
        while ((2 * index + 1) < length) {
            int leftIndex = 2 * index + 1;
            int rightIndex = 2 * index + 2;
            if (data.get(leftIndex) > data.get(index)
                    && data.get(leftIndex) > data.get(rightIndex)) {
                swap(leftIndex, index);
                index = leftIndex;
            } else if (data.get(rightIndex) > data.get(index)
                    && data.get(rightIndex) > data.get(leftIndex)) {
                swap(rightIndex, index);
                index = rightIndex;
            } else {
                break;
            }
        }
        return max;
    }

    public Integer extract1() {
        // 1. 获取第一个元素(最大值)
        // 2. 将最后一个元素挪到第一个元素上，进行下滤操作
        // 3. 获取左子节点和右子节点
        //      左子节点：(2 * index + 1)
        //      右子节点：(2 * index + 2)

        Integer max = data.get(0);
        data.set(0, data.get(length - 1));
        data.removeLast();
        length--;
        int index = 0;


        while ((2 * index + 1) < length) {
            int leftIndex = (2 * index + 1);
            int rightIndex = leftIndex + 1;
            int largeIndex = leftIndex;
            if (data.get(index) >= data.get(largeIndex)) {
                break;
            }
            if (data.get(rightIndex) > data.get(largeIndex)) {
                largeIndex = rightIndex;
            }

            swap(largeIndex, index);
            index = largeIndex;
        }

        return max;
    }

    public Integer peek() {
        return data.get(0);
    }

    public int size() {
        return length;
    }

    public boolean isEmpty() {
        return length == 0;
    }

    public void buildHeap(LinkedList<Integer> arr) {
        // 1. 从第一个非叶子结点开始，执行一次上滤操作
        // 获取第一个非叶子节点公式： ((length - 1) / 2)
        // 获取左子节点：(当前父元素下标 * 2) + 1
        // 获取右子节点：(当前父元素下标 * 2) + 2
        // 2. 第一个非叶子结点上滤完成后，在上滤第二个非叶子结点
        // 3. 以此类推，最终执行到根节点，然后对根节点做下滤操作
        this.data = arr;
        length = arr.size();
        // 9 11 20 56 23 45
        // 第一个叶子节点的下标
        int start = (arr.size() - 1) / 2;


        // 每个非叶子节点执行上滤操作
        while (start > 0) {
            int leftIndex = (start * 2) + 1;
            int rightIndex = leftIndex + 1;
            int largeIndex = leftIndex;
            // 检查下标是否越界
            // if (leftIndex >= length || rightIndex > length) break;

            if (arr.get(largeIndex) < arr.get(rightIndex >= length ? leftIndex : rightIndex)) {
                largeIndex = rightIndex;
            }

            swap(largeIndex, start);

            start--;
        }


        // 根节点执行下滤操作
        int index = 0;
        while ((index * 2 + 1) < length) {
            int leftIndex = index * 2 + 1;
            int rightIndex = leftIndex + 1;
            int largeIndex = leftIndex;
            // 检测下标是否越界
            if (leftIndex >= length || rightIndex >= length) break;

            if (arr.get(largeIndex) < arr.get(rightIndex)) {
                largeIndex = rightIndex;
            }
            if (arr.get(largeIndex) <= arr.get(index)) {
                break;
            }
            swap(largeIndex, index);
            index = largeIndex;
        }

    }

    public void buildHeap1(LinkedList<Integer> arr) {
        int start = (arr.size() - 1) / 2;
        length = arr.size();
        data = arr;
        for (int i = start; i >= 0; i--) {
            int index = i;
            while ((index * 2 + 1) < length) {
                int leftIndex = index * 2 + 1;
                int rightIndex = leftIndex + 1;
                int largeIndex = leftIndex;
                // 检测下标是否越界

                if (rightIndex < length && arr.get(largeIndex) <= arr.get(rightIndex)) {
                    largeIndex = rightIndex;
                }
                if (arr.get(largeIndex) < arr.get(index)) {
                    break;
                }
                swap(largeIndex, index);
                index = largeIndex;
            }
        }
    }

    @Override
    public String toString() {
        return "Heap{" +
                "data=" + data +
                '}';
    }

    public static void main(String[] args) {
        Heap heap = new Heap();
        // heap.insert(100);
        // heap.insert(75);
        // heap.insert(88);
        // heap.insert(60);
        // heap.insert(59);
        // heap.insert(77);


        // heap.insert(19);
        // heap.insert(100);
        // heap.insert(36);
        // heap.insert(17);
        // heap.insert(3);
        // heap.insert(25);
        // heap.insert(1);
        // heap.insert(2);
        // heap.insert(7);

        // 把当前元素添加到最后，然后再执行上滤操作
        // 获取父元素的位置(index - 1) / 2
        // 当前元素与父元素比较，如果比父元素大，则执行swap(当前元素位置,父元素位置)
        // 当前元素与父元素比较，如果比父元素小，则直接break


        // System.out.println(heap.extract());
        // System.out.println(heap.extract1());
        // System.out.println(heap);

        LinkedList<Integer> newHeap = new LinkedList<>();
        int[] arr = {
                9, 11, 20, 56, 23, 45
        };

        Arrays.stream(arr).forEach(newHeap::add);
        System.out.println("===================================");
        heap.buildHeap1(newHeap);
        System.out.println(heap);

    }

}
